0% completed
Problem Statement
Given a root of the binary tree and an integer S, return true if the tree has a path from root-to-leaf such that the sum of all the node values of that path equals S. Otherwise, return false.
Examples
Example 1:
- Input: root =
[1, 2, 3, 4, 5, 6, 7], S =10
- Expected Output:
true - Justification: The tree has
1 -> 3 -> 6root-to-leaf path having sum equal to 10.
Example 2:
- Input: root =
[12, 7, 1, 9, null, 10, 5], S =23
- Expected Output:
true - Justification: The tree has
12 -> 1 -> 10root-to-leaf path having sum equal to 23.
Example 3:
- Input: root =
[12, 7, 1, 9, null, 10, 5], S =16
- Expected Output:
false - Justification: The tree doesn't have root-to-leaf path having sum equal to 16.
Constraints:
- The number of nodes in the tree is in the range
[0, 5000]. -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
Solution
The Binary Tree Path Sum problem involves determining whether there is a root-to-leaf path in a binary tree such that the sum of the node values along the path equals a given target sum. The algorithm traverses the tree recursively, adjusting the target sum at each step by subtracting the value of the current node. At each step, we pass the updated target sum to the recursive DFS call. If a leaf node is reached and its value matches the adjusted sum, a valid path has been found.
Step-by-Step Algorithm
-
Check if the root is null:
- If the root is
null, returnfalsebecause there is no path in an empty tree.
- If the root is
-
Check if the current node is a leaf:
- If the current node is a leaf, and its value matches the current sum (target sum minus the values encountered so far), return
true, indicating that a valid path has been found.
- If the current node is a leaf, and its value matches the current sum (target sum minus the values encountered so far), return
-
Traverse the left and right subtrees:
- If the current node is not a leaf, adjust the sum by subtracting the value of the current node from the target sum.
- Recursively check both the left and right children, passing the updated sum to both recursive calls.
-
Return true if any recursive call returns true:
- If any of the recursive calls (left or right subtree) returns
true, returntrueto indicate that a valid path has been found. - Otherwise, return
falseif neither of the recursive calls finds a valid path.
- If any of the recursive calls (left or right subtree) returns
Algorithm Walkthrough
-
Step 1 - Start at the root node (12):
- The current node is
12. - The target sum is
23. - Check if the current node is
null: No. - Check if the current node is a leaf: No (it has left and right children).
- Subtract the current node's value from the target sum:
23 - 12 = 11. - Now recursively check both the left and right subtrees, with the new sum
11.
- The current node is
-
Step 2 - Traverse the left subtree (Node 7):
- The current node is
7. - The target sum is
11. - Check if the current node is
null: No. - Check if the current node is a leaf: No (it has a left child).
- Subtract the current node's value from the target sum:
11 - 7 = 4. - Now recursively check the left subtree with the new sum
4(as the right child is null).
- The current node is
-
Step 3 - Traverse the left subtree (Node 9):
- The current node is
9. - The target sum is
4. - Check if the current node is
null: No. - Check if the current node is a leaf: Yes (it has no left or right children).
- Check if the current node's value matches the target sum:
9 != 4. - Since the values do not match, return
falseand backtrack to node7.
- The current node is
-
Step 4 - Traverse the right subtree of Node 12 (Node 1):
- Backtrack to node
12and now traverse its right subtree. - The current node is
1. - The target sum is
11(from step 1). - Check if the current node is
null: No. - Check if the current node is a leaf: No (it has left and right children).
- Subtract the current node's value from the target sum:
11 - 1 = 10. - Now recursively check both the left and right subtrees with the new sum
10.
- Backtrack to node
-
Step 5 - Traverse the left subtree (Node 10):
- The current node is
10. - The target sum is
10. - Check if the current node is
null: No. - Check if the current node is a leaf: Yes (it has no left or right children).
- Check if the current node's value matches the target sum:
10 == 10. - Since the values match, return
trueindicating that a valid path (12 → 1 → 10) has been found.
- The current node is
-
Step 6 - Return final result:
- Since we found a valid path in step 5, the algorithm returns
truefor the input tree and sum23.
- Since we found a valid path in step 5, the algorithm returns
Final Output:
- The tree has a path with a sum of
23:12 → 1 → 10. Hence, the result istrue.
Code
Complexity Analysis
Time Complexity
The time complexity of the above algorithm is
Space Complexity
The space complexity of the above algorithm will be
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Final Output:
Code
Complexity Analysis
Time Complexity
Space Complexity